package com.datastructure3.array;

import org.junit.Test;

import java.awt.*;
import java.nio.file.FileStore;
import java.util.*;
import java.util.List;

/**
 * @author: 临晖
 * @since: 2024-05-31
 */
public class Solution {


    /**
     * 704. 二分查找
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
     *
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length;

        while (left < right) {
            int midIndex = (left + right) / 2;


            if (nums[midIndex] == target) {
                return midIndex;
            } else if (nums[midIndex] > target) {
                right = midIndex;
            } else {
                left = midIndex + 1;
            }
        }

        return -1;
    }


    /**
     * 35. 搜索插入位置
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     * 请必须使用时间复杂度为 O(log n) 的算法。
     *
     * @param nums
     * @param target
     * @return
     */
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return left;

    }


    /**
     * 34. 在排序数组中查找元素的第一个和最后一个位置
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
     * 如果数组中不存在目标值 target，返回 [-1, -1]。
     * 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        int front = -1;
        int end = -1;

        front = getLeft(nums, target);
        end = getRight(nums, target);

        if (front > end) {
            return new int[]{-1, -1};
        } else {
            return new int[]{front, end};
        }


    }

    //寻找左边界
    public int getLeft(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;


        while (left <= right) {
            int mid = left + ((right - left) / 2);

            if (nums[mid] >= target) {
                right = mid - 1;

            } else {
                left = mid + 1;
            }
        }

        return right + 1;
    }

    //寻找右边界
    public int getRight(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + ((right - left) / 2);
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return left - 1;
    }


    /**
     * 69. x 的平方根
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 提示
     * 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
     * <p>
     * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
     * <p>
     * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
     *
     * @param x
     * @return
     */
    public int mySqrt(int x) {

        if (x == 1) {
            return 1;
        }

        long left = 1;
        long right = x / 2;

        while (left <= right) {
            long midNum = left + ((right - left) / 2);

            if (midNum * midNum == x) {
                return (int) midNum;
            } else if (midNum * midNum > x) {
                right = midNum - 1;
            } else {
                left = midNum + 1;
            }
        }

        return (int) left - 1;
    }


    /**
     * 367. 有效的完全平方数
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
     * 完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。
     * 不能使用任何内置的库函数，如  sqrt 。
     *
     * @param num
     * @return
     */
    public boolean isPerfectSquare(int num) {
        if (num == 1) {
            return true;
        }

        long left = 1;
        long right = num / 2;

        while (left <= right) {
            long temp = left + ((right - left) / 2);
            long minNum = temp * temp;

            if (minNum == num) {
                return true;
            } else if (minNum > num) {
                right = temp - 1;
            } else {
                left = temp + 1;
            }
        }

        return false;
    }


    /**
     * 27. 移除元素
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 提示
     * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
     * 假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
     * 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
     *
     * @param nums
     * @param val
     * @return
     */
    public int removeElement(int[] nums, int val) {

        int slow = 0;
        int fast = 1;

        for (; fast < nums.length; fast++) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
        }

        return slow;
    }


    /**
     * 26. 删除有序数组中的重复项
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 提示
     * 给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
     * 考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
     * 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
     * 返回 k 。
     *
     * @param nums
     * @return
     */
    public int removeDuplicates(int[] nums) {
        int num = nums[0];
        int slow = 1;
        int fast = 1;
        for (; fast < nums.length; fast++) {
            if (nums[fast] != num) {
                nums[slow] = nums[fast];
                num = nums[slow];
                slow++;
            }
        }

        return slow;
    }


    /**
     * 283. 移动零
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 提示
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
     *
     * @param nums
     */
    public void moveZeroes(int[] nums) {
        int fast = 0;
        int slow = 0;

        for (; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                int temp = nums[fast];
                nums[fast] = nums[slow];
                nums[slow] = temp;
                slow++;
            }
        }
    }


    /**
     * 844. 比较含退格的字符串
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
     * 注意：如果对空文本输入退格字符，文本继续为空。
     *
     * @param s
     * @param t
     * @return
     */
    public boolean backspaceCompare(String s, String t) {
        if (s == null || t == null) {
            return true;
        }

        int sLen = s.length() - 1;
        int tLen = t.length() - 1;
        while (sLen >= 0 && tLen >= 0) {


            int sSpace = 0;
            int tSpace = 0;

            while (sLen >= 0) {
                if (s.charAt(sLen) == '#') {
                    sSpace++;
                    sLen--;
                } else if (sSpace > 0) {
                    sSpace--;
                    sLen--;
                } else {
                    break;
                }

            }

            while (tLen >= 0) {
                if (t.charAt(tLen) == '#') {
                    tSpace++;
                    tLen--;
                } else if (tSpace > 0) {
                    tSpace--;
                    tLen--;
                } else {
                    break;
                }

            }


            if (sLen < 0 && tLen < 0) {
                return true;
            } else if (sLen < 0 || tLen < 0) {
                return false;
            }

            if (s.charAt(sLen) != t.charAt(tLen)) {
                return false;
            }


            sLen--;
            tLen--;

        }


        if (tLen < 0 && sLen < 0) {
            return true;
        }

        return false;
    }


    /**
     * 977. 有序数组的平方
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
     *
     * @param nums
     * @return
     */
    public int[] sortedSquares(int[] nums) {
        int first = 0;
        int last = nums.length - 1;
        int[] res = new int[nums.length];
        int tempIndex = last;
        while (first <= last) {
            if (Math.abs(nums[first]) > Math.abs(nums[last])) {
                res[tempIndex] = nums[first] * nums[first];
                first++;
            } else {
                res[tempIndex] = nums[last] * nums[last];
                last--;
            }
            tempIndex--;
        }

        return res;
    }


    /**
     * 209. 长度最小的子数组
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个含有 n 个正整数的数组和一个正整数 target 。
     * 找出该数组中满足其总和大于等于 target 的长度最小的lkkml9uy8oijnmjiuoh
     * 子数组
     * [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
     *
     * @param target
     * @param nums
     * @return
     */
    public int minSubArrayLen(int target, int[] nums) {
        int res = Integer.MAX_VALUE;

        int firtIndex = 0;
        int lastIndex = 0;

        int sum = 0;
        for (; lastIndex < nums.length; lastIndex++) {
            sum += nums[lastIndex];

            while (sum >= target) {
                res = Math.min(lastIndex - firtIndex + 1, res);
                sum -= nums[firtIndex];
                firtIndex++;
            }
        }

        return res == Integer.MAX_VALUE ? 0 : res;

    }


    /**
     * 904. 水果成篮
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
     * 你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
     * 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
     * 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
     * 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
     * 给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
     *
     * @param fruits
     * @return
     */
    public int totalFruit(int[] fruits) {

        //水果种类，水果数量
        HashMap<Integer, Integer> map = new HashMap<>();

        int slow = 0;
        int fast = 0;

        int maxRes = Integer.MIN_VALUE;
        int sum = 0;
        for (; fast < fruits.length; fast++) {
            map.put(fruits[fast], map.getOrDefault(fruits[fast], 0) + 1);
            sum++;


            while (map.size() > 2) {
                int count = map.get(fruits[slow]) - 1;
                if (count > 0) {
                    map.put(fruits[slow], count);
                } else {
                    map.remove(fruits[slow]);
                }

                slow++;
                sum--;
            }

            maxRes = Math.max(maxRes, ++sum);


        }

        return maxRes;
    }


    /**
     * 76. 最小覆盖子串
     * 已解答
     * 困难
     * 相关标签
     * 相关企业
     * 提示
     * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
     *
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        if (t.length() > s.length()) {
            return "";
        }

        int slow = 0;
        int fast = 0;

        //存储字符串t
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) + 1);
        }

        //返回值
        String resStr = s;
        boolean flag = false;


        //开始判断
        int len = 0;
        int lenT = t.length();
        Map<Character, Integer> map2 = new HashMap<>();
        for (; fast < s.length(); fast++) {
            //添加
            map2.put(s.charAt(fast), map2.getOrDefault(s.charAt(fast), 0) + 1);
            len++;

            //如果添加的字符多于t，且s完全包含t
            while (len >= lenT && isContain(map2, map)) {
                flag = true;
                //截取字符串
                String temp = s.substring(slow, fast + 1);

                if (resStr.length() > temp.length()) {
                    resStr = temp;
                }


                //
                Integer value = map2.get(s.charAt(slow));
                value--;
                if (value == 0) {
                    map2.remove(s.charAt(slow));
                } else {
                    map2.put(s.charAt(slow), value);
                }
                slow++;
                len--;
            }
        }

        if (flag) {
            return resStr;
        }

        return "";
    }

    public boolean isContain(Map<Character, Integer> map1, Map<Character, Integer> map2) {

        Set<Map.Entry<Character, Integer>> entrySet = map2.entrySet();

        for (Map.Entry entry : entrySet) {
            char key2 = (char) entry.getKey();

            Integer value1 = map1.getOrDefault(key2, 0);

            if (value1 < (Integer) entry.getValue()) {
                return false;
            }
        }

        return true;
    }


    /**
     * 59. 螺旋矩阵 II
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
     *
     * @param n
     * @return
     */
    //public int[][] generateMatrix(int n) {
    //    //定义数组
    //    int[][] matrix = new int[n][n];
    //
    //    int count = n / 2 + 1;
    //
    //    int left = 0;
    //    int right = n - 1;
    //    int first = 0;
    //    int last = n -1 ;
    //
    //    int start = 0;
    //    while (count-- > 0) {
    //        //上
    //
    //        int y = left;
    //        for (; y <= right; y++) {
    //            matrix[first][y] = ++start;
    //        }
    //
    //        //右
    //        y--;
    //        first++;
    //        int x = first;
    //        for (; x <= last; x++) {
    //            matrix[x][y] = ++start;
    //        }
    //
    //        right--;
    //        x--;
    //        //下
    //        y = right;
    //        for (; y >= left; y--) {
    //            matrix[x][y] = ++start;
    //        }
    //
    //        last--;
    //        y++;
    //
    //        //左
    //        x = last;
    //        for (; x >= first; x--) {
    //            matrix[x][y] = ++start;
    //        }
    //
    //        left++;
    //        x++;
    //    }
    //
    //
    //    return matrix;
    //}
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];

        int x = 0;
        int y = 0;
        int offset = 1;
        int count = 1;

        int i = 0;
        int j = 0;
        for (int num = 0; num < n / 2; num++) {         //循环圈数

            for (; j < n - offset; j++) {
                res[i][j] = count++;
            }

            for (; i < n - offset; i++) {
                res[i][j] = count++;
            }

            for (; j > y; j--) {
                res[i][j] = count++;
            }

            for (; i > x; i--) {
                res[i][j] = count++;
            }

            x++;
            y++;
            offset++;

        }

        if (n % 2 == 1) {
            res[n / 2][n / 2] = count;
        }

        return res;
    }


    /**
     * 54. 螺旋矩阵
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 提示
     * 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
     *
     * @param matrix
     * @return
     */
    public static List<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> list = new ArrayList<>();
        int m = matrix.length;
        int n = matrix[0].length;

        //y
        int left = 0;
        int right = n - 1;

        //x
        int height = 0;
        int low = m - 1;

        while (true) {
            int i;
            int j;
            //上
            for (j = left; j <= right; j++) {
                list.add(matrix[height][j]);
            }

            if (++height > low) {
                break;
            }
            //右

            for (i = height; i <= low; i++) {
                list.add(matrix[i][right]);
            }

            if (--right < left) {
                break;
            }

            //下
            for (j = right; j >= left; j--) {
                list.add(matrix[low][j]);
            }

            if (--low < height) {
                break;
            }


            //左
            for (i = low; i >= height; i--) {
                list.add(matrix[i][left]);
            }

            if (++left > right) {
                break;
            }


        }

        return list;

    }


    /**
     *
     * LCR 146. 螺旋遍历二维数组
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给定一个二维数组 array，请返回「螺旋遍历」该数组的结果。
     * 螺旋遍历：从左上角开始，按照 向右、向下、向左、向上 的顺序 依次 提取元素，然后再进入内部一层重复相同的步骤，直到提取完所有元素。
     *
     * @param array
     * @return
     */
    public int[] spiralArray(int[][] array) {

        if (array.length == 0) {
            return new int[]{};
        }


        int m = array.length;
        int n = array[0].length;
        int[] list = new int[m * n];
        int index = 0;

        //y
        int left = 0;
        int right = n - 1;

        //x
        int height = 0;
        int low = m - 1;

        while (true) {
            int i;
            int j;
            //上
            for (j = left; j <= right; j++) {
                list[index++] = array[height][j];
            }

            if (++height > low) {
                break;
            }
            //右

            for (i = height; i <= low; i++) {
                list[index++] = array[i][right];
            }

            if (--right < left) {
                break;
            }

            //下
            for (j = right; j >= left; j--) {
                list[index++] = array[low][j];
            }

            if (--low < height) {
                break;
            }


            //左
            for (i = low; i >= height; i--) {
                list[index++] = array[i][left];
            }

            if (++left > right) {
                break;
            }


        }

        return list;
    }

    @Test
    public void myTest() {
        int[][] matrix = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
        spiralOrder(matrix);
    }


}

//1 1 1 1
//1 1 1 1
//1 1 1 1
//1 1 1 1


